The present invention relates to the field of computer networks and to the backup of digital data in such networks.
The present invention relates more particularly to a method, a system, and a device for the distributed backup of data in a network that does not include a server dedicated to backup operations. The invention proposed distributes the backup tasks over a set of storage elements connected to the network, while also implementing mechanisms for persistently preserving the control and check data and the stored digital data. The aim is to create a peer-to-peer network in which many terminals connected to the Internet join forces to provide a perennial storage service. Each microcomputer acts as a storage peripheral. If the microcomputer fails, is stolen, or is damaged, the information stored will be retrievable even if said microcomputer is replaced with a new one.
In the prior art, US Patent Application US 2004/0 049 700 (Takeo Yoshida) discloses an inexpensive data storage method using available capacity in personal computers (PCs) connected to the network. When a backup client of a user PC receives a backup instruction for a file from a user, the backup client requests backup to a backup control server. The backup control server divides and encrypts the file to be backed up into a plurality of encrypted pieces, transfers the encrypted pieces to user PCs, and stores the encrypted pieces in the hard disk drives (HDDs) of the user PCs. When the distributively backed up file is to be extracted, the user PC obtains each of the encrypted pieces from the user PCs on which they are stored, and combines and decrypts the encrypted pieces to restore the original file.
That proposed solution is to distribute data storage by dispersing the data over a set of peripherals connected to the network. However, that system requires high availability of the peripherals, or at least that they be activatable remotely, in order to access the data. The other drawback of that system is that it does not make it possible to overcome failure of the storage peripherals, and loss of data on a storage peripheral is irremediable. Finally, that system is not scalable because storage is coordinated by a server via which all of the data passes.
Also in the prior art, PCT Patent Application WO 02/063 484 (SS8 Networks) discloses a distributed data storage system whose architecture is highly available and highly scalable. In one embodiment of that invention, the distributed data storage system includes a plurality of data storage units that are controlled by an object management system. The object management system selects the distributed data storage units for performing the file access requests according to the external inputs/outputs with which the file access requests are associated. In response to a file creation request that is associated with an external input of one distributed data storage unit, the object management system preferentially creates a data file in that distributed data storage unit. In response to a file retrieval request that is associated with a data file and with an external output of a distributed data storage unit, the object management system preferentially returns a hostname and a pathname of a copy of the data file that is stored within that distributed data storage unit. The object management system also makes redundant copies of the data files in different units to provide high availability of data. In that patent application, the system performs redundant distributed storage that nevertheless requires a centralized management system that can be likened to a management server. That proposed solution is not viable without the presence of such a server, which makes it extremely dependent on the server operating properly.
US Patent Application US 2002/0 114 341 (Andrew Sutherland et al.) also discloses a peer-to-peer storage system including a storage coordinator that centrally manages distributed storage resources in accordance with system policies administered through a central administrative console. The storage resources are otherwise unused portions of storage media, e.g. hard disks, that are included in the devices such as personal computers, workstations, laptops, file servers, and so forth, that are connected to a computer network. That patent application proposes distributed storage in a network requiring the presence of a storage coordinator, i.e. a sort of server, that distributes the data to be stored to the various devices or nodes of the network.
Similarly, US Patent Application US 2004/064 693 (Akhil K. Arora, et al.) discloses a distributed index mechanism for indexing and searching for identity information in peer-to-peer networks. A distributed index, of the distributed hash table (DHT) type may be used to store identity information in a decentralized manner on a plurality of peer nodes. The identity information may be used, for example, to authenticate users. Distributed indexes may allow identity information to be spread across multiple peer nodes so that the load is spread among the various peer nodes. That patent application proposes using the DHT to put in place a distributed identification mechanism (for identifying users or for some other identification purpose). The peers of a DHT are made active (by requests for authentication information) so as not to restrict storage to mere passive storage, but the use of them does not go beyond that context and does not make it possible to detect failures on another node.
In the state of the art, peer-to-peer networks are also known that use DHTs, such as Chord, CAN, Pastry or Tapestry, for implementing distributed data storage. The use of DHTs in such networks offers a routing mechanism for routing between the peers via an overlay network or “overlay” that tolerates failures and that is more resistant to attacks related to the routing-overlay association. It also offers a dictionary that is distributed and redundant over the overlay: each input of the dictionary is made up of a key and of an associated object (e.g. a digital data file). The object is inserted into the DHT which replicates it over various nodes in order to guarantee a certain level of tolerance to failures. The use of the DHT also offers a logic organization for the data: a single identifier is assigned to each of the peers, ideally the identifiers are chosen such that they are as dispersed as possible in the space of the available names, and a function (e.g. identity) projects the space of the keys of the dictionary into the space of the names of the peers. On inserting a new object into the DHT dictionary, the peer that stores it is the peer that is reached by the routing algorithm as a function of the projected key of the object in the names space; in general, the routing algorithm designates the peer that has the identifier that is closest to the projection of the key. The inserted object is replicated by the DHT so as to overcome disappearance of peers. Typically, each peer maintains a list of peers that have “neighboring” (in the meaning of the routing algorithm) identifiers in the names space, the object is then duplicated over those peers. The known mechanisms associated with the DHTs make it possible to manage the data merely by primitives such as “search”, “put”, “get”, “free”, etc. Another limitation concerns the “cumbersomeness” of use of DHTs: they store the data, which considerably increases the traffic over the network when requests are transmitted.
An object of the present invention is to remedy the drawbacks of the prior art by proposing a method of distributed backup that distributes backup in a computer network, and that is based on the use of distributed hash tables for storing the control and check or storage management information in persistently perennial manner. The term “control and check or storage management information” is used to mean all of the data that is associated with the data to be stored, in the nodes of the network, and that is used during data storage or during data retrieval.
The method of the present invention copes particularly well with the problems of current computer networks: scaling the network by adding new nodes or by removing old nodes, security from attacks, data protection, redundancy of storage information, persistent preservation of data in the event of failures or defects. To this end, the invention provides, in its most general acceptation, A method for the distributed backup for backing up a block B of digital data distributively in a computer network including a distributed hash table DHT and at least three nodes NO, the nodes NO being connected to said network, said method comprising a subdivision step for subdividing said block B into r fragments F of digital data, said method being characterized in that it further comprises the following steps:                a storage step for storing a fragment F in the storage resources of a node NOF; and        a recording step for recording the pairs (block B, node NOF) and (node NOF, fragment F) in the portions of the DHT that are contained in at least two nodes;        and, during said method, no operation on the DHT or any storage operation is implemented on a centralized server.        
In an implementation, after the subdivision step, said method further comprises a step of computing s redundancy fragments computed on the basis of said r fragments F. In a particular implementation, said fragments are stored, during the storage step, in nodes that are all different. Particularly, the DHT contains check data only, and no fragment of data.
In an implementation, said method further comprises a periodic sending step whereby each of said nodes periodically sends activity information to a set of nodes selected by the DHT. In an implementation, the DHT contains a “life cycle” field, and sending said activity information updates the “life cycle” field of said node, said field being present in every one of the nodes selected by the DHT. In a particular implementation, said method further comprises a detection step for detecting a “life cycle” field that is not updated by a node Cfailed. Particularly, said method further comprises a reconstruction step for reconstructing the data stored in said failed node Cfailed and for updating, in the DHT, the list of the nodes storing at least one fragment of said block B.
In an implementation, each of the fragments reconstructed during said reconstruction step is stored in at least one other healthy node. In a particular embodiment, said method further comprises a recovery step for recovering said block B. Particularly, said recovery step comprises a first step of sending a request from the requesting node to the DHT, a second step in which the DHT sends back to it the nodes that are storing the fragments of the block, a step of sending a request for recovering fragments to said nodes, and a step of reconstructing the block B as of reception of F different fragments.
The invention also provides a distributed data backup device for implementing the method, said device comprising a processor, a storage memory, connection means for connecting to the network, and means for controlling the distributed data, of the distributed hash table DHT type. In an embodiment, said device is in the form of an external box that is added to an existing a computer workstation. The invention also provides a distributed backup system comprising at least two preceding devices connected together via a computer network. Particularly, said system comprises a plurality of devices connected to a plurality of interconnected networks.